This disclosure relates generally to data processing, and more particularly to algorithms and systems for drawing directed acyclic graphs.
Directed Acyclic Graphs (DAG) are used to represent information in many disciplines such as software applications, communication networks and web data analysis. Nicely drawn graphs make it easy to visualize and comprehend the represented information. We will use the term “Aesthetics of Graph” to refer to the how nicely the nodes are laid out and edges are drawn.
There is no objective measure of aesthetics for graph layouts. However based on hand-made drawings, it is observed that avoiding edge crossings and congestion, keeping short and straight edges, and favoring geometry and symmetry are principles or goals that lead to aesthetically better graphs. It is very hard to optimize all of these aesthetics goals simultaneously. In fact, it is computationally intractable (NP-hard) to minimize edge crossings or to maximize graph symmetry. This has led to many heuristic-based algorithms that try to satisfy the above aesthetic principles.
Graph drawing has long been a topic of research, and there have been many papers published on both “graph drawing” and various “aesthetic principles.” Most iterative graph drawing algorithms use compaction as one of their steps. Typically Quadratic Programming methods are used to achieve compaction, which can turn out to be very computationally intensive. This is a deterrent in applications where graphs are drawn and re-drawn frequently. Therefore, there is a need for algorithms which are fast and achieve good compaction.